package zw_401_500.zw_463_岛屿的周长;

class Solution {

    public static void main(String[] args) {
        int[][] grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}};
        int perimeter = islandPerimeter(grid);
        System.out.println(perimeter);
    }


    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ans += dfs(i, j, grid, n, m);
                }
            }
        }
        return ans;
    }

    public static int dfs(int x, int y, int[][] grid, int n, int m) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) {
            return 0;
        }
        grid[x][y] = 2;
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            res += dfs(tx, ty, grid, n, m);
        }
        return res;
    }



//    public int islandPerimeter(int[][] grid) {
//        // 下个格子的x轴与y轴加的值，右下左上
//        int[] dx = {0, 1, 0, -1};
//        int[] dy = {1, 0, -1, 0};
//        // n表示高度，m表示宽度
//        int n = grid.length, m = grid[0].length;
//        int ans = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                if (grid[i][j] == 1) {
//                    int cnt = 0;
//                    for (int k = 0; k < 4; k++) {
//                        int tx = i + dx[k];
//                        int ty = j + dy[k];
//                        // tx < 0，已是左边界；tx >= n，已是右边界
//                        // ty < 0，已是上边界；ty >= m，已是下边界
//                        // grid[tx][ty] == 0，相邻格子是水域
//                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
//                            cnt += 1;
//                        }
//                    }
//                    ans += cnt;
//                }
//            }
//        }
//        return ans;
//    }
}
